package sort;

import java.util.Arrays;

/**
 * 描述:基数排序
 *
 *
 * @author
 * @created 2022/1/6 18:58
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        /*定义10个桶，为了防止数据溢出，每个桶的大小都是数组的长度*/
        int[][] bucket = new int[10][arr.length];
        /*定义一个数组用来存桶中的数据数量*/
        int[] bucketElementCounts = new int[10];
        /*先得出数组中最大数的位数*/
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int maxlength = (max + "").length();
        /*循环处理*/
        /*针对每个元素的位进行排序*/
        for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                /*取出每个元素的位*/
                int digitOfElement = (arr[j] / n) % 10;
                /*放入到对应的桶中*/
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            /*按照桶的顺序（一维数组的下标一次取出数据，放入原来的数组）*/
            int index = 0;
            /*遍历每一个桶，并将桶中的数据放入原数组*/
            for (int k = 0; k < bucketElementCounts.length; k++) {
                /*如果桶中有数据，我们才放入到原来的数组中*/
                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                /*第i+1伦处理后，需要对每一个bucketElementCounts[k]置为0*/
                bucketElementCounts[k] = 0;
            }
        }
    }

}
